from Algo import SortAlgo

"""
查找算法集合
"""


# 二叉查找
def binsearch(key, l=None):
    if l is None:
        print("please enter list")
        return
    # 冒泡排序
    SortAlgo.bubblesort(l)
    start = 0
    end = len(l) - 1
    while start <= end:
        mid = (start + end) // 2
        if key == l[mid]:
            return mid
        elif key > l[mid]:
            start = mid + 1
        elif key < l[mid]:
            end = mid - 1
    if start >= end:
        return -1


# 递归
def binsearch_rec(key, start, end, l=None):
    if start > end:
        return -1
    mid = (start + end) // 2
    if key > l[mid]:
        return binsearch_rec(key, mid + 1, end, l)
    elif key < l[mid]:
        return binsearch_rec(key, start, mid - 1, l)
    elif key == l[mid]:
        return mid


def exec_binsearch():
    l = [1, 2, 3]
    key = 3
    index = binsearch(key, l)
    print("{} 在 {} 的位置是 {}".format(key, l, index))


def exec_binsearch_rec():
    l = [1, 3]
    key = 3
    SortAlgo.bubblesort(l)
    index = binsearch_rec(key, 0, len(l), l)
    print("{} 在 {} 的位置是 {}".format(key, l, index))


if __name__ == "__main__":
    exec_binsearch_rec()
    # exec_binsearch()
